package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-02-10 20:24
 **/
public class LeetCode1447 {

    public List<String> simplifiedFractions(int n) {
        List<String> res = new ArrayList<>();
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                if (gcd(j, i) == 1) {
                    res.add("" + j + "/" + i);
                }
            }
        }
        return res;
    }

    //求最大公约数
    int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }

}
